package jzOffer;

public class Num45 {
    public String minNumber(int[] nums) {
        String[] str=new String[nums.length];
        for(int i=0;i<nums.length;i++){
            str[i]=String.valueOf(nums[i]);
        }
        quickSort(str,0,str.length-1);
        StringBuilder sb=new StringBuilder();
        for(String s:str){
            sb.append(s);
        }
        return sb.toString();
    }
    private void quickSort(String[] str,int i,int j){
        if(i>=j) return;
        int p=partition(str,i,j);
        quickSort(str,i,p-1);
        quickSort(str,p+1,j);
    }
    private int partition(String[] str,int l,int r){
        int pivot=l;//基准值
        int j=l;
        for(int i=l;i<=r;i++){
            if((str[i]+str[pivot]).compareTo(str[pivot]+str[i])<0){
                if(i!=j) swap(str,j+1,i);
                j++;
            }
        }
        swap(str,j,pivot);
        return j;
    }
    private void swap(String[] str,int x,int y){
        String tmp=str[x];
        str[x]=str[y];
        str[y]=tmp;
    }
}
